import sun.reflect.generics.tree.Tree;

import java.io.Reader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    int i =0;
    TreeNode root = null;
    public TreeNode createTree(String s) {
      TreeNode root = null;
      if(s.charAt(i) != '#'){
          root = new TreeNode(s.charAt(i));
          i++;
          createTree(s);
          createTree(s);
      }
      else{
          i++;
      }//
      return root;
    }
    public void preOrder(TreeNode root) {
        if(root==null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }//
    void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }//
    void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }//
    public static int nodeSize;
    void size(TreeNode root) {
        if(root==null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }//遍历方法//
    int size2(TreeNode root) {
        if(root==null){
            return 0;
        }
        return size2(root.left) + size2(root.right)+1;
    }//子问题//
    public static int leafSize = 0;
    void getLeafNodeCount1(TreeNode root) {
         if(root.left==null && root.right == null){
           leafSize++;
           return;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }//
    int getLeafNodeCount2(TreeNode root) {
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }//
    int getKLevelNodeCount(TreeNode root, int k) {
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
       return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }//
    int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        int lefttree = getHeight(root.left);
        int righttree = getHeight(root.right);
        return righttree>lefttree ? righttree +1:lefttree+1;
    }//
    TreeNode find(TreeNode root, char val) {
if(root==null){
    return null;
}
if(root.val==val){
    return root;
}
TreeNode ret1 = find(root.left,val);
if(ret1 != null){
    return ret1;
}
TreeNode ret2 = find(root.right.right,val);
if(ret2 != null){
    return ret2;
}
return null;
    }//
    void levelOrder(TreeNode root) {
        List<List<Integer>> lists = new LinkedList<>();
        if(root==null){
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<Integer>();
            int size =queue.size();
            for(int i =0;i<size; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                TreeNode left = node.left;
                TreeNode right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            lists.add(0,list);

        }
        System.out.println(lists);
    }//
    boolean isCompleteTree(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
           TreeNode ret =queue.poll();
           if(ret != null){
               queue.offer(ret.left);
               queue.offer(ret.right);
           }
           else {
               break;
           }
        }
        while(!queue.isEmpty())
        {
            if(queue.poll() != null){
                return false;
            }
        }
        return true;
    }
}
